2018-08-20

分治

分治法，递归求解一个问题，在每一层递归中应用分解，解决和合并三个步骤。

分解

将问题划分为子问题，子问题的形式与原问题一样，只是规模更小。

解决

如果子问题的规模足够小，则停止递归，直接求解

合并

将子问题的解组合成原问题的解

有时除了与原问题形式完全一样的规模更小的子问题外，还需要求解与原问题不完全一样的子问题，这些可以在合并步骤完成，

最大子数组

二叉树遍历

前序（根左右）

####　非递归

栈保存的是访问树节点的顺序，先进后出。入栈表示先不访问节点，出栈表示访问该节点。将当前指针指向的节点又看做根节点。

先序遍历二叉树的时候，首先访问根结点，再访问左孩子，最后访问右孩子。

在二叉树先序遍历非递归算法中:

先将根结点压栈，在栈不为空的时候执行循环;
让栈顶元素p出栈，访问栈顶元素p;
如果p的右孩子不为空，则让其右孩子先进栈
如果p的左孩子不为空，则再让其左孩子进栈

(注意：进栈顺序一定是先右孩子，再左孩子)

void preOrder(TreeNode *t){
    if(t==nullptr)return;
    stack<TreeNode*> stk;
    TreeNode *p=t;
    stk.push(p);
    while(!stk.empty()){
        p=stk.top();
        stk.pop();
        cout<<p->val<<" ";//访问根节点
        //注意入栈顺序
        if(p->right)stk.push(p->right);//右子节点先入栈
        if(p->left)stk.push(p->left);
    }
}

void preOrder(TreeNode *t){
    if(t==nullptr)return;
    stack<TreeNode*> stk;
    TreeNode *p=t;
    while(p!=nullptr||!stk.empty()){
        while(p!=nullptr){
            cout<<p->val<<" ";//先访问根节点
            stk.push(p);
            p=p->left;  //再访问左子节点
        }
        if(!stk.empty()){
            p=stk.top();
            stk.pop();
            p=p->right; //右节点进行同样的操作，可以为空节点
        }
        
    }
}

中序（左根右）

非递归

栈保存的是访问树节点的顺序，先进后出。入栈表示先不访问节点，出栈表示访问该节点。将当前指针指向的节点又看做根节点。

中序遍历的顺序是从最左节点开始的，所以需要将根节点的左节点全部入栈，直到最左节点(即左子节点为空)也入栈，将最左节点出栈进行访问，然后将当前的指针P指向栈顶结点的右孩子，使其作为根节点继续相同的处理。

刚开始指针指向树的根节点。将节点入栈后将指针指向左子节点，表示的是优先访问左子节点，先不访问根节点。
继续入栈根节点，直到左子节点为空，就表示没有左子树了。
将栈顶元素出栈，表示访问该节点，即左子节点为空的根节点。
按照中序遍历规则，输出该节点。
将指针指向该节点的右子节点，表示访问右子树。继续遍历。

void InOrder_NoRecur(TreeNode *t){
    if(t==nullptr)return;
    stack<TreeNode*> stk;
    TreeNode *p=t;
    while(p!=nullptr||!stk.empty()){
        while(p!=nullptr){//将节点的左子树全部遍历
            stk.push(p);
            p=p->left;
        }
        if(!stk.empty()){
            p=stk.top();  //添加空栈判断加强鲁邦性if(!stk.empty()){}
            stk.pop();
            cout<<p->val<<" ";
            p=p->right;　//转换到右节点，可以为空节点          
        }
    }
}

参考

后序（左右根）

非递归

后序遍历的非递归实现是三种遍历方式中最难的一种。

后序遍历也是最左节点开始遍历，所以需要从根结点开始，将所有最左结点全部压栈，每当一个结点出栈时，都先扫描该结点的右子树，只有当一个结点的左孩子和右孩子结点均被访问过了，才能访问结点自身。

辅助变量：

ｆｌａｇ＝１表示当前结点的左孩子为空或者已被访问
ＴｒｅｅＮｏｄｅ　*ｐｒｅ：表示之前访问的节点

void postOrder(TreeNode *t){
    if(t==nullptr)return;
    stack<TreeNode*> stk;
    TreeNode *p=t;  //当前指针指向的节点
    
    int flag=0;　//标识位，用来表示左子节点已经被访问　或者　左子节点为空
    TreeNode *pre;  //前驱节点，表示访问过的节点
    
    do{
        while(p!=nullptr){　//所有最左节点入栈，从最左节点开始
            stk.push(p);
            p=p->left;
        }
        flag=1;
        pre=nullptr;　//指向当前节点的前驱节点
        while(!stk.empty() && flag==1){　//当左子树已经被访问或者为空时，存在两种情况：
            p=stk.top(); //只获取栈顶元素，不出栈访问。因为还存在两种情况：
            if(p->right==pre){ //１：节点的右子节点为空　或者　右子节点已经被访问过
                stk.pop();　//出栈访问该节点
                cout<<p->val<<" ";　
                pre=p;　　//表示该节点访问过了
            } else {//２：右子节点不为空，则先处理右子节点
                p=p->right;
                flag=0;
            }
        }
    }while(!stk.empty()); //有分号，使用dowhile是因为
}

该算法具有一个特性：就是当访问某个结点时，栈中所保存的元素正好是这个结点的所有祖先。

那么知道了这个特性，我们就很容易解决下面如下问题：

(1).当给定一个叶子结点，要求输出该叶子结点的所有祖先

(2).输出根结点到所有叶子结点的路径

(3).如果二叉树结点的值是数值，那么求每条路径上值之和，也可以利用二叉树后序遍历的非递归算法这个特性

参考

二叉树深度

问题：给定一个二叉树，求它的深度。

分解：树的深度可以分解为（左子树深度＋１）（右子树深度＋１）取其中的最大值。

解决：递归条件是空树返回０。

合并：可以采用参数返回，也可以采用ｖｏｉｄ。

int DepthOfTree(TreeNode *t){
    if(t==nullptr)return 0;
    int left_depth=DepthOfTree(t->left)+1;
    int right_depth=DepthOfTree(t->right)+1;
    return max(left_depth,right_depth);
}

判断平衡树（ＡＶＬ）

平衡二叉树(AVL)：

它或者是一颗空树；

或者具有以下性质的二叉树：

每个节点的左子树和右子树的深度之差(平衡因子)的绝对值不超过1。
它的左子树和右子树都是一颗平衡二叉树。

分解：根节点判断，左子节点判断，右子节点判断。这三种情况是问题一样但规模不同

解决：空树返回真，利用求二叉树深度函数进行判断

合并：根据ＡＶＬ树的定义，只有在左右子树深度不超过１＆＆左子树符合要求＆＆右子树也符合要求，才能返回真。

最直接的求法：遍历二叉树，求每一个节点的左右子树深度做判断。时间复杂度是$O(N^2)$，太费时间。

（1）如果二叉树为空，返回真

（2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假

bool IsAVL(TreeNode *t){
    if(t==nullptr)return true;//空树返回真
    int ld=DepthOfTree(t->left);
    int rd=DepthOfTree(t->right);
    if(ld-rd>=-1 && ld-rd<=1 && IsAVL(t->left) && IsAVL(t->right))return true;
    return false;
}

$O(N)$求法：遍历二叉树是不可避免的，所以应该在求深度的地方优化。采用后序遍历的方式（左右根），在左右子节点的时候顺便求深度即可优化算法，也就是自底向上遍历。

关键在于如何在遍历左右子节点时求深度：递归的时候需要保存左右子树的深度信息，~~需要额外的两个变量~~。在合并的时候只需要一个变量来保存深度就可以了。

bool IsAVL(TreeNode *t,int &deep){
    if(t==nullptr){
        deep=0;　//deep用于保存处理节点的深度。
        return true;
    }
    /*
    bool left=IsAVL(t->left,deep);//先访问处理左子树
    int ld=deep; //处理完左子树后的深度，也就是左子树的深度
    bool right=IsAVL(t->right,deep);//再访问处理右子树
    int rd=deep;　//右子树的深度
    //处理根节点：左子树是AVL ＆＆ 右子树也是AVL ＆＆ 根节点的左右深度不超过１
    if(left && right && ld-rd>=-1 && ld-rd<=1){
        deep=(ld>rd)?ld+1:rd+1;  //返回上层时深度是左右子树深度的最大值要加１
        return true;
    }
    return false;   
    */
    int ld,rd;
    //左右子树做了递归，不用再考虑，只需考虑根节点处理
    if(IsAVL(tree->left,ld)&&IsAVL(tree->right,rd)&&ld-rd>=-1&&ld-rd<=1){
        deep=(ld>rd)?ld+1:rd+1;
        return true;
    }
    return false;
}

BST转双向链表

BST(Binary Sort Tree)，二叉排序树，又名二叉查找树，又名二叉搜索树

它或者是一棵空树；

或者是具有下列性质的二叉树：

若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
左、右子树也分别为二叉排序树；

题目：输入一棵二叉搜索树，将其转换为一个排序的双向链表。要求：不能创建任何新的结点，只能调整树中结点指针的指向。

分析：

输入：二叉树根节点指针ＴｒｅｅＮｏｄｅ　*ｒｏｏｔ
输出：双向链表，应该指明头节点，即返回一个指针指向双向链表的第一个元素，需要一个指针变量ｈｅａｄ指向头节点，该指针不能随着函数变化，所以应该设置全局指针。
递归截止：返回ｎｕｌｌｐｔｒ
将左右子节点链接起来需要知道前一个节点信息，所以需要一个变量ｐｒｅ保存前一个节点。要保证每次调用ｐｒｅ的指向不变。可以使用指针的指针或者全局变量
ｐｒｅ指向前一个节点，ｃｕｒ指向当前处理的根节点，进行连接即可。
右子树进行同样的操作。也就是递归处理右子树（当前根节点变成了右子节点）

TreeNode *head=nullptr;
void BSTtoList(TreeNode *t){
    TreeNode *pre=nullptr;
    transform(t,&pre);//取pre指针的地址，指针的指针
}

void transform(TreeNode *t,TreeNode **pre){
    if(t==nullptr)return nullptr;
    
    transform(t->left,pre);//先处理左子树
    
    //
    TreeNode *cur=t; //cur指向当前访问的节点(根节点)
    if(*pre==nullptr){//在最左节点处
        *pre=cur;
        head=cur;//指向第一个指针
    } else {//连接两个节点
        cur->left=*pre;
        (*pre)->right=cur;
        *pre=cur;
    }
    
    transform(t->right,pre);
    
}

本文标题:分治

文章作者:ITS-Ma

发布时间:2018年08月20日 - 10时08分

最后更新:2018年08月22日 - 16时51分

原始链接:https://itsma.github.io/[object Object]/divideconquer.html

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。